#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int V = 25010;
int a[N];
bool f[V];
int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    int m = a[n - 1], res = 0;
    memset(f, 0, sizeof(f));
    f[0] = true;
    for (int i = 0; i < n; ++i) {
      if (f[a[i]]) continue;
      res++;
      for (int j = a[i]; j <= m; ++j) {
        f[j] |= f[j - a[i]];
      }
    }
    cout << res << endl;
  }
}
